package com.Oct_Night;

import java.util.ArrayList;
import java.util.List;

/**
 * 剑指 Offer II 085. 生成匹配的括号
 * 正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * https://leetcode.cn/problems/IDBivT/
 *
 * 2022/10/09 12:51
 */

public class Solution085 {

    List<String> list=new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        dfs("",0,0,n);
        return list;
    }
    void dfs(String sb,int count1,int count2,int n) {
        if (count1 > n || count2 > n) return;
        if (count1 == n && count2 == n) list.add(sb);
        if (count1 >= count2) {
            dfs(sb+"(", count1 + 1, count2, n);
            dfs(sb+")", count1, count2 + 1, n);
        }
    }

    public static void main(String[] args) {
        Solution085 solution085=new Solution085();
        System.out.println(solution085.generateParenthesis(3));
    }
}
